from cmath import inf
from functools import cache
from typing import List

# 记忆化搜索
# 子问题： 对于 当前点 可以拆分为 选 or 不选
# 考虑其中编号最大的点7 用[选 or 不选] 分类讨论：
# 不选： 问题变成不经过7的最短路，也就是中间节点<=6 的最短路
# 选： 问题分解成从 2 到 7 的最短路， and 7 到 1 的最短路。这两最短路的中间节点都不包含7，也就是中间节点<=6 的最短路
# 定义 dfs（k,i,j） ： 表示 从i到j 的最短路长度，并且这条最短路的中间节点编号都 <=k。 注意中间节点不包含i和j

# 状态转移方程  min（不选 ，选）
# dfs（k,i,j） = min(dfs(k-1,i,j),dfs(k-1,i,k)+dfs(k-1,k,j))
# 递归边界：dfs（-1，i，j）=w[i][j], k=-1 表示 i和j 之间没有任何节点，此时最短路长度只能是连接 i和j 的边的边权，即w[i][j]。如果没有边权 则w[i][j]=inf （无穷大）
# 递归入口：dfs(n−1,i,j)，表示从 i 到 j 的最短路长度。k=n−1 是因为本题节点编号为 0 到 n−1，任意最短路的中间节点编号都 ≤n−1。
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        w = [[inf] * n for _ in range(n)]
        for x, y, wt in edges:
            w[x][y] = w[y][x] = wt

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        # 起点i 终点j ，中间节点k
        def dfs(k: int, i: int, j: int) -> int:
            if k < 0:  # 递归边界
                return w[i][j]
            # 转台转移方程
            return min(dfs(k - 1, i, j), dfs(k - 1, i, k) + dfs(k - 1, k, j))

        ans = 0
        min_cnt = inf
        for i in range(n):
            cnt = 0
            for j in range(n):
                if j != i and dfs(n - 1, i, j) <= distanceThreshold:
                    cnt += 1
            if cnt <= min_cnt:  # 相等时取最大的 i
                min_cnt = cnt
                ans = i
        return ans


# 1：1 翻译成 dp 动态规划
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        w = [[inf] * n for _ in range(n)]
        for x, y, wt in edges:
            w[x][y] = w[y][x] = wt

        # 定义三维数组
        f = [[[0] * n for _ in range(n)] for _ in range(n + 1)]
        # f[0]的状态 = dfs（-1，i，j） 的时候 表示 递归边界
        f[0] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    f[k + 1][i][j] = min(f[k][i][j], f[k][i][k] + f[k][k][j])

        ans = 0
        min_cnt = inf
        for i in range(n):
            cnt = 0
            for j in range(n):
                if j != i and f[n][i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= min_cnt:  # 相等时取最大的 i
                min_cnt = cnt
                ans = i
        return ans

# 空间优化
# 观察上面的状态转移方程，在计算 f[k+1] 时，只会用到 f[k]，不会用到（第一个维度的）下标小于 k 的状态。
# 能不能像 0-1 背包那样，把第一个维度去掉呢？也就是
#
# f[i][j]=min(f[i][j],f[i][k]+f[k][j])
# 不幸的是，我们无法确定 k 和 i,j 的大小关系，上式中的 f[i][k] 的值可能是 f[k][i][k]，也有可能被覆盖成了 f[k+1][i][k]。同样的，f[k][j] 的值也可能被覆盖成了 f[k+1][k][j]
#
# 但是！从状态的定义来看：
# f[k+1][i][k] 表示从 i 到 k 的最短路长度，并且这条最短路的中间节点编号都 ≤k。由于终点是 k，那么中间节点必然不包含 k，所以中间节点编号都 ≤k−1，所以 f[k+1][i][k]=f[k][i][k] 成立
# 同理，f[k+1][k][j]=f[k][k][j]。
# 因为值没变，所以不用担心被覆盖，直接去掉第一个维度。
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        w = [[inf] * n for _ in range(n)]
        for x, y, wt in edges:
            w[x][y] = w[y][x] = wt

        f = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # f[i][j] = min(f[i][j], f[i][k] + f[k][j])
                    # 手动 if 比大小更快
                    s = f[i][k] + f[k][j]
                    if s < f[i][j]:
                        f[i][j] = s

        ans = 0
        min_cnt = inf
        for i in range(n):
            cnt = 0
            for j in range(n):
                if j != i and f[i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= min_cnt:  # 相等时取最大的 i
                min_cnt = cnt
                ans = i
        return ans
